這門課的目的在於學習演算法設計的六個基本策略，如下所示。

　•　Greedy Method
　•　Dynamic Programming (DP)
　•　Prune-and-Search (P&S)
　•　Branch-and-Bound (B&B)
　•　Divide-and-Conquer (D&C)
　•　Plane Sweep

這門課有二次程式考試。第一次考試要求同學設計一個能解決 the longest
common subsequence problem 的 DP 程式與一個能解決 2-d linear
programming problem 的 P&S 程式。第二次考試要求同學設計一個能解決
the 0/1 knapsack problem 的 B&B 程式與一個能解決 2-d closest pair
problem 的 D&C 程式。以上四個 problems 與其相對應的演算法在課堂上將
會詳細介紹。

這二次考試在期末有一次補考機會(程式抄襲者與被抄襲者將喪失補考機會)。
若補考成績低於或等於原始成績，則以原始成績作為最終成績。若補考成績
高於原始成績，則以
"原始成績+(補考成績-原始成績)x90%" 作為最終成績。

同學必須閱讀以下四篇論文(DP、P&S、B&B、D&C 各一篇)，並繳交書面
閱讀報告。

　•　(DP) Wagner, "The string-to-string correction problem," Journal of the
　 　ACM, vol.21, no.1, 1974, 168-173.
　•　(P&S) Megiddo, "Linear-time algorithms for linear programming in R3
　 　and related problems," SIAM Journal on Computing, vol.12, no.4,
　 　1983, 759-776 (only Section 3 is required).
　•　(B&B) A personal assignment problem solved by the branch-and-
　 　bound strategy (in Section 5-6 of Lee, Tseng, Chang and Tsai's
　 　book: Introduction to the Design and Analysis of Algorithms).
　•　(D&C) Imai, Iri, and Murota, "Voronoi diagram in the Laguerre
　 　geometry and its applications," SIAM Journal on Computing,
　 　vol.14, no.1, 1985, 93-105.

每篇閱讀報告必須包含(但不限)以下內容，且必須用例子與圖表輔助說明。

　•　問題定義
　•　解法敘述(勿列出詳細程式碼)
　•　讀後心得

閱讀報告請以中文書寫(可夾雜英文專有名詞)，勿剪貼原始論文內容拼湊
而成，應忠實地將自己所理解的內容寫出。例子與圖表可援用原始論文或
自創，敘述方式不必遵循原著可自創。陳老師將親自批閱同學的閱讀報告，
評分依據如下。

　•　態度(是否用心書寫？)
　•　能力(是否看懂論文且掌握重點？是否敘述清楚且精簡扼要？是否使用合適
　 　的例子與圖表輔助說明？)

此外，同學將分成八組研讀以下八篇論文(DP 三篇、P&S 一篇、B&B 與 D&C 各
二篇)並在課堂上報告。

　•　(DP) Knuth, "Optimal binary search trees," Acta Informatica, vol.1, 1971,
　 　14-25.
　•　(DP) Hsu and Du, "New algorithms for the LCS problem," Journal of
　 　Computer and System Sciences, vol.29, 1984, 133-152.
　•　(DP) Wang, Chen, and Park, "On the set LCS and set-set LCS problems,"
　 　Journal of Algorithms, vol.14, no.3, 1993, 466-477. (ignore Section 3: 　
　 　The Set LCS Problem)
　•　(P&S) Bhattacharya, Jadhav, Mukhopadhyay, and Robert, "Optimal
　 　algorithms for some intersection radius problems," Computing, vol.52,
　 　no.3, 1994, 269-279. (ignore Section 2: Intersection Radius Problem
　 　for Hyperplanes)
　•　(B&B) Wang and Lee, "An Efficient Channel Routing Algorithm to Yield
　 　an Optimal Solution," IEEE Transactions on computers, vol.39, no.7,
　 　1990, 957-962.
　•　(B&B) Section 5-9 of Lee, Tseng, Chang and Tsai's book: Introduction to
　 　the Design and Analysis of Algorithms.
　•　(D&C) Güting, "Optimal divide-and-conquer to compute measure and
　 　contour for a set of iso-rectangles," Acta Informatica, vol.21, 1984,
　 　271-291.
　•　(D&C) Lee, "An optimal time and minimal space algorithm for rectangle
　 　intersection problems," International Journal of Computer and Information
　 　Sciences, vol.15, no.1, 1984, 23-32.

所有論文皆有電子檔供下載。針對同學的報告，老師將會給予適當建議
(若有需要)，相信對同學日後職場生涯有所助益。